package course.p11_graph.s1_disjointSet;

import java.util.Arrays;

/**
 * 并查集(不相交集)数据结构学习
 */
public class DisjointSet {

    /**
     * 找到指定位置的根节点
     * @param array
     * @param ele
     * @return
     */
    public int findRoot(int[] array,int ele){
        int x_root = ele;
        // 查找ele的根
        while (array[x_root] != -1) {
            x_root = array[x_root];
        }
        return x_root;
    }

    /**
     * 此方法尝试合并x,y到数组array中
     * 1--成功的合并  0--合并失败
     * @param x x
     * @param y y
     * @param array 数组
     * @return
     */
    public int isUnion(int x,int y,int[] array) {
        int x_root = findRoot(array,x);
        int y_root = findRoot(array,y);
        // 当x,y拥有相同的父节点，
        // 意味着他们已经合并在一起了
        if(x_root == y_root) {
            return 0;
        }
        //执行合并操作
        else{
            array[y_root] = x_root;
            return 1;
        }
    }

    /**
     * 数组初始化
     * @param parent
     */
    void init(int[] parent){
        Arrays.fill(parent, -1);
    }


}
